PalindromePartitioning.java

packagesection19_DynamicProgramming;

/*
 * Given a string s, partition s such that every substring of the partition is a palindrome.
 Return the minimum cuts needed for a palindrome partitioning of s. [Leetcode 132]
 */
importjava.util.Arrays;

publicclassPalindromePartitioning {

publicstaticvoidmain(String[] args) {

Stringsource = "abacdc";
intstartIndex = 0, endIndex = source.length() - 1;
System.out.println(palindromePartitionRec(source, startIndex, endIndex));

Stringsrc = "abacdce";
System.out.println(palindromePartitionRec(src, 0, src.length() - 1));

int[][] strg = newint[src.length()][src.length()];
for (inti = 0; i < strg.length; i++) {
Arrays.fill(strg[i], -1);
 }
System.out.println("using top down for small input");
System.out.println(palindromePartitioningTopDownDP(src, 0, src.length() - 1, strg));

System.out.println("\ntesting large inputs");

Strings = "aeirahsdvmzxklncaodgnasadasdsafhioashdffoihokn";
// System.out.println(palindromePartitionRec(s, 0, s.length() - 1));

int[][] storage = newint[s.length()][s.length()];
for (inti = 0; i < storage.length; i++) {
Arrays.fill(storage[i], -1);
 }
System.out.println(palindromePartitioningTopDownDP(s, 0, s.length() - 1, storage));

System.out.println("\nusing bottom up dp");

System.out.println(palindromePartitioningBottomUpDP("aba")); // 0
System.out.println(palindromePartitioningBottomUpDP(source)); // 1
System.out.println(palindromePartitioningBottomUpDP("abacdce")); // 2
System.out.println(palindromePartitioningBottomUpDP(s)); // 38

 }

publicstaticintpalindromePartitionRec(Stringstr, intsi, intei) {

if (isPalindrome(str, si, ei)) {
return0;
 }
intminCut = Integer.MAX_VALUE;

for (intcalls = si; calls < ei; calls++) {

intfirstHalf = palindromePartitionRec(str, si, calls);
intsecondHalf = palindromePartitionRec(str, calls + 1, ei);

intans = firstHalf + secondHalf + 1;

if (ans < minCut) {
minCut = ans;
 }
 }

returnminCut;
 }

publicstaticbooleanisPalindrome(Stringstr, intsi, intei) {
intlow = si, high = ei;
while (low < high) {
if (str.charAt(low) != str.charAt(high))
returnfalse;
low++;
high--;
 }
returntrue;
 }

publicstaticintpalindromePartitioningTopDownDP(Stringstr, intsi, intei, int[][] storage) {

if (isPalindrome(str, si, ei)) {
return0;
 }
intminCut = Integer.MAX_VALUE;

if (storage[si][ei] != -1) { // reuse
returnstorage[si][ei];
 }
for (intcalls = si; calls < ei; calls++) {

intfirstHalf = palindromePartitioningTopDownDP(str, si, calls, storage);
intsecondHalf = palindromePartitioningTopDownDP(str, calls + 1, ei, storage);

intans = firstHalf + secondHalf + 1;

if (ans < minCut) {
minCut = ans;
 }
 }
storage[si][ei] = minCut; // store solution in problem index

returnminCut;
 }

publicstaticintpalindromePartitioningBottomUpDP(Stringstr) {
boolean[][] palindromeStorageReuse = palindromeStorage(str);

intlen = str.length();
int[][] storage = newint[len][len];

// filling direction
for (intslide = 0; slide <= len - 1; slide++) {

for (intsi = 0; si <= len - slide - 1; si++) {

intei = si + slide;

// logic from top down
// optimizing this task to check palindrome for each cell
if (palindromeStorageReuse[si][ei]) {
storage[si][ei] = 0;
 } else {
intminCut = Integer.MAX_VALUE;

for (intcalls = si; calls < ei; calls++) {

intfirstHalf = storage[si][calls];
intsecondHalf = storage[calls + 1][ei];

intans = firstHalf + secondHalf + 1;

if (ans < minCut) {
minCut = ans;
 }
 }

storage[si][ei] = minCut; // store solution in problem index
 }
 }
 }

returnstorage[0][len - 1];
 }

// optimizing base case to check palindrome for each cell
publicstaticboolean[][] palindromeStorage(Stringstr) {
intn = str.length();
boolean[][] palindromeInfo = newboolean[n][n];

for (inti = 0; i < palindromeInfo.length; i++) {
Arrays.fill(palindromeInfo[i], true);
 }

for (introw = n - 2; row >= 0; row--) {

for (intcol = row + 1; col < n; col++) {

if (str.charAt(row) == str.charAt(col)) {
palindromeInfo[row][col] = palindromeInfo[row + 1][col - 1];
 } else {
palindromeInfo[row][col] = false;
 }
 }
 }

returnpalindromeInfo;
 }
}